package com.zhugang.week13.sorting;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @program algorithms
 * @description: BucketSort
 * @author: chanzhugang
 * @create: 2022/09/30 23:16
 */
public class BucketSort {

    /**
     * 桶排序：每个桶里的数据相同
     * O(n)
     *
     * @param A
     * @return
     */
    public List<Integer> sort(List<Integer> A) {
        int k = 100;
        List<LinkedList<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            // 构建k个桶(桶用LinkedList表示)
            buckets.add(new LinkedList<>());
        }

        for (Integer num : A) {
            // 取模放入对应的桶
            buckets.get(num % k).add(num);
        }

        List<Integer> result = new ArrayList<>();
        for (LinkedList<Integer> bucket : buckets) {
            // 遍历k个桶
            result.addAll(bucket);
        }
        return result;
    }
}